package 中等.其他;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。
 * 一次煎饼翻转的执行过程如下：
 * 选择一个整数 k ，1 <= k <= arr.length
 * 反转子数组 arr[0...k-1]（下标从 0 开始）
 * 例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。
 * 以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length
 * 范围内的有效答案都将被判断为正确。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/pancake-sorting
 */
public class 煎饼排序_969 {

    public static void main(String[] args) {

        int[] arr = new int[]{3, 2, 4, 1};
        System.out.println(new 煎饼排序_969().pancakeSort(arr));

    }

    /**
     * 类选择排序
     * 思路：找出[0,i-1]中最大的值，放到i-1的位置
     * 实现：
     * 1，找到最大值的索引，然后进行翻转，将最大值放至0索引
     * 2，以i-1进行翻转，将最大值，放至i-1处，i-1为排序好的位置
     * 注意：
     * 如果最大值索引直接为i-1无需做任何动作
     * 最大值为索引0位置，则减少一次翻转
     * k是1-length不是索引！！！
     *
     * @param arr
     * @return
     */
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int end = arr.length - 1; end > 0; end--) {  //0-i为需要进行排序的空间
            int maxIndex = 0;
            for (int j = 0; j <= end; j++) {  //找出最大值索引
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }
            if (maxIndex == end) continue;
            if (maxIndex != 0) {
                list.add(maxIndex + 1);
                replace(arr, 0, maxIndex);
            }
            list.add(end + 1);
            replace(arr, 0, end);
        }
        return list;
    }

    public void replace(int[] arr, int from, int to) {
        while (from < to) {
            int temp = arr[to];
            arr[to] = arr[from];
            arr[from] = temp;
            from++;
            to--;
        }
    }

}
